﻿#include "MargeSort.h"

void MargeSort::sort(vector<int>& arr)
{
	int length = arr.size();

	if (length < 2) return;

	progress(arr, 0, length - 1);
}

void MargeSort::progress(vector<int>& arr, int left, int right)
{
	if (left == right)
	{
		return;
	}
	int mid = left + ((right - left) >> 1);
	progress(arr, left, mid);
	progress(arr, mid + 1, right);
	marge(arr, left, right, mid);
}

void MargeSort::marge(vector<int>& arr, int left, int right, int mid)
{
	vector<int> help;

	int p1 = left;
	int p2 = mid + 1;

	while (p1 <= mid && p2 <= right)
	{
		help.push_back(arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]);
	}

	while (p1 <= mid)
	{
		help.push_back(arr[p1++]);
	}

	while (p2 <= right)
	{
		help.push_back(arr[p2++]);
	}

	for (int i = 0; i < right - left + 1; i++)
	{
		arr[i + left] = help[i];
	}

	help.clear();
}